//编写一个算法来判断一个数 n 是不是快乐数。 
//
// 「快乐数」 定义为： 
//
// 
// 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。 
// 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。 
// 如果这个过程 结果为 1，那么这个数就是快乐数。 
// 
//
// 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 19
//输出：true
//解释：
//1² + 9² = 82
//8² + 2² = 68
//6² + 8² = 100
//1² + 0² + 0² = 1
// 
//
// 示例 2： 
//
// 
//输入：n = 2
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 2³¹ - 1 
// 
//
// Related Topics 哈希表 数学 双指针 👍 1488 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author ldltd
 * @date 2023-12-20 20:41:09
 * @description 202.快乐数
 */
public class HappyNumber{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new HappyNumber().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*数字不会无限增大，999的下一位是243，*/
    public boolean isHappy1(int n) {

		//set也可能无限循环导致存储太多
		int [] tem=new int[]{0,1,4,9,16,25,36,49,64,81};
		Set<Integer> set=new HashSet<>();
		int sum=0;
		while (true){
			sum=0;
			while (n!=0){
				sum+=tem[n%10];
				n/=10;
			}
			if(sum==1){
				return true;
			}else if(set.contains(sum)){
				return false;
			}else {
				n=sum;
				set.add(sum);
			}
		}

    }
	public int HappyHelper(int n){
		int sum=0;
		while (n>0){
			int bit=n%10;
			sum+=bit*bit;
			n=n/10;
		}
		return sum;
	}
	//快慢指针，fast每次走两步，有循环就会和slow相等，或者走到终点都等于1
	public boolean isHappy2(int n) {
		int slow=n,fast=n;
		do{
			slow=HappyHelper(slow);
			fast=HappyHelper(fast);
			fast=HappyHelper(fast);
		}while (slow!=fast);
		return slow==1;
	}

	/*数学，只有一个循环
	* 4→16→37→58→89→145→42→20→4
	* 所有其他数字都在进入这个循环的链上，或者在进入 111 的链上。*/
	private  Set<Integer> cycleMembers =
			new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));

	public int getNext(int n) {
		int totalSum = 0;
		while (n > 0) {
			int d = n % 10;
			n = n / 10;
			totalSum += d * d;
		}
		return totalSum;
	}


	public boolean isHappy(int n) {
		while (n != 1 && !cycleMembers.contains(n)) {
			n = getNext(n);
		}
		return n == 1;
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
